package com.ddshuai.easy;

/**
 * @author ddshuai
 * @version 1.0.0
 * @date 2018/3/29
 * @modify desc
 * @2018/3/29 新增        1.0.0
 * <p>
 * 给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。
 * <p>
 * 例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
 * 连续子序列 [4,-1,2,1] 的和最大，为 6。
 * <p>
 * 扩展练习:
 * <p>
 * 若你已实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 */
public class MaxSubArray {

    /**
     * 普通解法
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length, dp = nums[0], max = dp;
        for (int i = 1; i < len; ++i) {
            dp = nums[i] + (dp > 0 ? dp : 0);
            if (dp > max) {
                max = dp;
            }
        }
        return max;
    }

    /**
     * 分治法
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {
        if (left >= right) {
            return nums[left];
        }

        int mid = (left + right) >> 1;
        int leftAns = helper(nums, left, mid);
        int rightAns = helper(nums, mid + 1, right);
        int leftMax = nums[mid], rightMax = nums[mid + 1];
        int temp = 0;
        for (int i = mid; i >= left; --i) {
            temp += nums[i];
            if (temp > leftMax) {
                leftMax = temp;
            }
        }
        temp = 0;
        for (int i = mid + 1; i <= right; ++i) {
            temp += nums[i];
            if (temp > rightMax) {
                rightMax = temp;
            }
        }
        return Math.max(Math.max(leftAns, rightAns), leftMax + rightMax);
    }

    public static void main(String[] args) {
        System.out.println(new MaxSubArray().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(new MaxSubArray().maxSubArray(new int[]{-2, 1, 0}));
        System.out.println("######################分治法############################");
        System.out.println(new MaxSubArray().maxSubArray1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(new MaxSubArray().maxSubArray1(new int[]{-2, 1, 0}));
    }
}
